package stack;

public class Q20 {

	public boolean isValid(String s) {
		java.util.Stack<Character> stack = new java.util.Stack<Character>();
		for(int i = 0 ; i < s.length() ; i++) {
			char temp = s.charAt(i);
			if(temp == '(' || temp == '[' || temp == '{') {
				stack.push(temp);
			}else {
				if(stack.isEmpty())
					return false;
				char popChar = stack.pop();
				if(temp == ')' && popChar != '(')
					return false;
				if(temp == ']' && popChar != '[')
					return false;
				if(temp == '}' && popChar != '{')
					return false;
			}
		}
		return stack.isEmpty();
    }
	
	public static void main(String[] args) {
		System.out.println(new Q20().isValid("()[]{"));
	}
}
